package com.lyt.springboot.util.algorithm;

import org.junit.Test;

import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;

public class SN1 {
    public static void main(String[] args) {
        SN1 sn1 = new SN1();
        String s = "aa";
//        sn1.inorderTraversal();
        System.out.println();
    }

    public String trans(String s, int n) {
        StringBuilder builder = new StringBuilder();
        String[] arr = s.split(" ");
        for (int i = arr.length - 1; i >= 0; i--) {
            String a = reverse(arr[i]);
            builder.append(a);

            if (i == 0) {
                break;
            }
            builder.append(" ");

        }
        return builder.toString();
    }

    public String reverse(String s) {
        char[] charArray = s.toCharArray();
        StringBuilder builder = new StringBuilder();
        for (char c : charArray) {
            if (Character.isUpperCase(c)) {
                char c0 = Character.toLowerCase(c);
                builder.append(c0);
            } else if (Character.isLowerCase(c)) {
                char c1 = Character.toUpperCase(c);
                builder.append(c1);
            }

        }
        return builder.toString();

    }

    @Test
    public void test() {
        String a = "ffffabcde";
        int abc = a.indexOf("abc");
        System.out.println(abc);
    }

    @Test
    public void test1() {
        SN1 sn1 = new SN1();
        sn1.longestCommonPrefix(new String[]{"abcdefgh", "aefghijk", "abcefgh"});

    }

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String commonPrefis = strs[0];
        int i = 1;
        while (i <= strs.length - 1) {
            while (strs[i].indexOf(commonPrefis) != 0) {
                commonPrefis = commonPrefis.substring(0, commonPrefis.length() - 1);
                if (commonPrefis == "") {
                    return "";
                }
            }
            i++;
        }
        return commonPrefis;
    }

    public String solve(String IP) {
        return vaildeV4Address(IP) ? "IPv4" : vaildeV6Address(
                IP) ? "IPv6" : "Neither";

    }

    public boolean vaildeV4Address(String ipAddress) {
        String[] ipArr = ipAddress.split("\\.", -1);
        if (ipArr.length != 4) {
            return false;
        }
        for (String ip : ipArr) {
            if (ip.startsWith("0") && ip.length() > 0) {
                return false;
            }
            try {
                Integer a = Integer.parseInt(ip);
                if (a < 0 || a > 255) {
                    return false;
                }
            } catch (Exception e) {
                return false;
            }
        }

        return true;
    }

    public boolean vaildeV6Address(String ipAddress) {
        String[] ipArr = ipAddress.split(":", -1);
        if (ipArr.length != 8) {
            return false;
        }
        for (String ip : ipArr) {
            if (ip.length() > 4 || ip.length() == 0) {
                return false;
            }
            try {
                Integer a = Integer.parseInt(ip, 16);
            } catch (Exception e) {
                return false;
            }
        }
        return true;
    }

    public String solveByJava(String s, String t) {
        BigInteger num1 = new BigInteger(s);
        BigInteger num2 = new BigInteger(t);
        return num1.add(num2).toString();
    }

    @Test
    public void test2() {
        List<Integer> numbers = Arrays.asList(5, 3, 8, 1, 2);
        Collections.sort(numbers);
        System.out.println(numbers);
        numbers.sort((a, b) -> b - a);
        System.out.println(numbers);
        Collections.sort(numbers, (a, b) -> b - a); // 从大到小排序
        System.out.println(numbers);
    }

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });
        ArrayList<Interval> arrList = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            return arrList;

        }
        //定义指针pre cur
        int pre = 0;
        int cur = 1;
        int size = intervals.size();
        while (cur < size) {
            if (intervals.get(pre).end >= intervals.get(cur).start) {
                int end = Math.max(intervals.get(pre).end, intervals.get(cur).end);
                intervals.set(pre, new Interval(intervals.get(pre).start, end));
                intervals.remove(cur);
                size--;
            } else {
                pre++;
                cur++;
            }
        }
        return intervals;
    }

    public class Interval {
        int start;
        int end;

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }


    public String solve0(String str) {
        if (str.length() == 0 || str.length() == 1) {
            return str;
        }
        StringBuilder builder = new StringBuilder();
        char[] charArray = str.toCharArray();
        for (int i = charArray.length - 1; i >= 0; i--) {
            builder.append(charArray[i]);

        }
        return builder.toString();
    }

    public int maxLength(int[] arr) {
        int left = 0;
        int right = 0;
        int max = 0;
        HashSet<Integer> set = new HashSet<>();
        while (right < arr.length) {
            if (set.contains(arr[right])) {
                set.remove(arr[left++]);
            } else {
                set.add(arr[right++]);
                max = Math.max(max, set.size());
            }
        }
        return max;
    }

    public int[] FindNumsAppearOnce(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            }
        }
        Set<Integer> set = map.keySet();
        List<Integer> list = new ArrayList<>();
        for (Integer num : set) {
            list.add(num);

        }
        int[] arr1 = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr1[i] = list.get(i);
        }
        return arr1;
    }

    public int minNumberDisappeared(int[] nums) {
        int[] arr = new int[nums.length + 1];
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] <= nums.length && nums[i] > 0) {
                arr[nums[i]] = 1;
            }
        }
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i] == 0) {
                return i;
            }
        }
        return arr.length;
    }

//    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
//    ArrayList<ArrayList<Integer>> result0 = new ArrayList<>();
//    ArrayList<Integer> res = new ArrayList<>();
//    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
//        Arrays.sort(num);
//        dfs(num,0);
//       for(ArrayList<Integer> arrayList:result){
//           if(!result0.contains(arrayList)) {
//               result0.add(arrayList);
//           }
//       }
//        return result0;
//    }
//    public void dfs(int[] nums,int depth){
//        if(nums.length == depth){
//            result.add(new ArrayList<>(res));
//            return;
//        }
//        for (int i = 0; i < nums.length; i++) {
//            if(!res.contains(nums[i])) {
//                res.add(nums[i]);
//                depth++;
//                dfs(nums,depth);
//                res.remove(res.size()-1);
//                depth--;
//            }
//        }
//    }


    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    ArrayList<Integer> arrayList = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        dfs(num, 0, new boolean[num.length]);
        ArrayList<ArrayList<Integer>> result0 = new ArrayList<>();
        for (ArrayList<Integer> arr : result) {
            if (!result0.contains(arr)) {
                result0.add(arr);
            }
        }
        return result0;
    }

    public void dfs(int[] num, int depth, boolean[] used) {
        if (num.length == depth) {
            result.add(new ArrayList<>(arrayList));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (!used[i]) {
                arrayList.add(num[i]);
                used[i] = true;
                dfs(num, depth + 1, used);
                //回退
                arrayList.remove(arrayList.size() - 1);
                used[i] = false;
            }

        }
    }

    StringBuilder builder = new StringBuilder();
    ArrayList<String> list = new ArrayList<>();
    char[] charArray;
    boolean[] used;

    public ArrayList<String> Permutation(String str) {
        if (str == null || str.length() == 0) {
            return new ArrayList<>();

        }
        charArray = str.toCharArray();
        used = new boolean[charArray.length];
        dfs(builder, 0, used);
        ArrayList<String> list0 = (ArrayList<String>) list.stream().distinct().collect(Collectors.toList());
        Set<String> set = new LinkedHashSet<>(list);
        ArrayList<String> uniqueList = new ArrayList<>(set);
        return list0;

    }

    public void dfs(StringBuilder builder, int depth, boolean[] used) {
        if (builder.length() == charArray.length) {
            list.add(new String(builder.toString()));
            return;
        }
        for (int i = 0; i < charArray.length; i++) {
            if (!used[i]) {
                builder.append(charArray[i]);
                used[i] = true;
                dfs(builder, depth + 1, used);
                //回退
                used[i] = false;
                builder.deleteCharAt(builder.length() - 1);
            }

        }
    }

    @Test
    public void test3() {
        int[][] a = {
                {1, 2, 3},
                {5, 6, 7, 8},
                {9, 10, 11, 12}
        };
        System.out.println(a[0].length);
    }

    List<Integer> listq = new ArrayList<>();

    public int[] inorderTraversal(TreeNode root) {
        dfs(root);
        int[] arr = new int[listq.size()];
        for (int i = 0; i < listq.size(); i++) {
            arr[i] = listq.get(i);
        }
        return arr;
    }

    public void dfs(TreeNode root) {
        if (root != null) {
            dfs(root.left);
            listq.add(root.val);
            dfs(root.right);
        }
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    @Test
    public void test4() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.add(3);
        queue.add(2);
        System.out.println(queue);

        PriorityQueue<Integer> queue1  = new PriorityQueue<>(((o1, o2) -> o1 - o2));
        queue1.add(4);
        queue1.add(3);
        queue1.add(2);
        queue1.add(9);
        queue1.add(8);
        queue1.add(7);
        queue1.add(1);
        System.out.println(queue1);
        List<Integer> arr2 = new ArrayList<>(queue1);
        System.out.println(arr2);
        while (!queue1.isEmpty()) {
            System.out.println(queue1.poll());
        }
    }
//    @Test
//    public ArrayList<ArrayList<Integer>> test5(TreeNode root) {
//        //层序遍历
//        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
//        Queue<TreeNode> queue = new LinkedList<>();
//        if(root==null) {
//            return  res;
//        }
//        ArrayList<Integer> list = new ArrayList();
//        int n = queue.size();
//        while(queue!=null) {
//
//        }
//        return res;
//    }

    @Test
    public void test6() {
        List<String> list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        String a = list.size() %2 == 0 ? list.get(list.size()/2-1) : list.get(list.size()/2);
        System.out.println(list.get(list.size()/2));
    }

}